% \subsection{Полиномиальной сложности принтер-комбинаторы с выбором}

\subsection{Оптимальное форматирование как задача BURS}

Для снижения алгоритмической сложности задачи поиска
оптимального представления документа, заданного комбинаторами из \cite{swierstra},
можно произвести сведение к BURS.
Сведение основано на следующих наблюдениях.
Пусть $w$ есть максимальная допустимая
ширина вывода. Поскольку каждая возникающая раскладка представляется блоком
текста, для поиска оптимального представления можно рассматривать
все промежуточные раскладки
как тройки $(n, k, h)$, где $n \le w$ --- это общая ширина раскладки, $k \le n$ ---
ширина ее последней строчки, $h$ --- ее высота. Тогда очевидно, что при $h_1 \le h_2$
между $(n, k, h_1)$ и $(n, k, h_2)$ первая тройка предпочтительней на любом этапе вычислений.
Таким образом для каждого узла не может быть более $w^2$ существенных представлений\footnote{
На самом деле, из-за ограничения $k \le n$ максимальное число раскладок не $w^2$, a
$\frac{w^2 + w}{2}$, но это несущественно.}.

Документ, для которого мы ищем раскладку, можно рассматривать как дерево, построенное из примитивов
\lstinline[language=Haskell]{text},
\lstinline[language=Haskell]{indent},
\lstinline[language=Haskell]{beside},
\lstinline[language=Haskell]{above} и \lstinline[language=Haskell]{choice}. Тогда задачу
раскладки документа можно решать независимо для поддеревьев, а потом объединять решения
при учете, что для каждого поддерева
и каждой пары $(n, k), k \le n \le w$ запоминается такая минимальная $h$, что для поддерева существует
текстовое представление с размерами $(n, k, h)$. Тогда, совершив обход дерева снизу вверх, мы сможем
вычислить оптимальное представление для всего дерева. Полезно заметить,
что оптимальное представление дерева не всегда получается из оптимальных представлений его
поддеревьев, поскольку при использовании поддеревьев возникают дополнительные
ограничения на ширину раскладок этих поддеревьев.

Приведенные наблюдения можно формализовать в виде BURS-задачи.
Для заданной ширины вывода $w$ введем набор нетерминалов
$T_n^k$, для всех $k \le n \le w$. Определим BURS-грамматику так, чтобы цена вывода $h$ нетерминала
$T_n^k$ для документа соответствовала его раскладке с параметрами $(n, k, h)$.
Для такой BURS-грамматики этап разметки посчитает все существенные раскладки, а этап свертки
вернет оптимальную. Определим правила переписывания для этой грамматики:
\begin{enumerate}
\item Для терминального узла $[\mbox{\lstinline{text s}}]$\footnote{
  Квадратные скобки используются для обозначения терминалов, состоящих из одного
  или нескольких символов.}
  существует два варианта:
  \begin{itemize}
     \item Если $|s|\le w$ (где $|s|$ --- это длина строки $s$), то вводится единственное правило
           $T^{|s|}_{|s|}: [\mbox{\lstinline{text s}}]$ со стоимостью $1$;           
           для всех остальных
           $k, n\ne |s|$ используется $T^k_n:[\mbox{\lstinline{text s}}]$ со стоимостью $\infty$;
     \item Если $|s| > w$, то вводится правило $T^k_n:[\mbox{\lstinline{text s}}]$ со стоимостью\
       $\infty$ для всех $k, n$.
  \end{itemize}
  Действительно, раскладка документа, состоящего из строчки длины $|s|$, может быть только размеров
  $(|s|, |s|, 1)$. Все остальные размеры недоступны, поэтому имеют стоимости $\infty$.

\item Для узла $[\mbox{\lstinline{indent m}}]$ введем два набора правил:
  \begin{enumerate}
     \item $T^{k+m}_{n+m}:[\mbox{\lstinline{indent m}}]\:(T^k_n)$ со стоимостью,
       равной стоимости раскладки поддерева $m$ в $T_n^k$, для всех $n$ 
     и $k$ таких, что $n+m\le w$ и $k\le n$;
     \item $T^k_n:[\mbox{\lstinline{indent m}}]\:(T^i_j)$ со стоимостью $\infty$ в противном случае.
  \end{enumerate}
  Понятно, что сдвиг раскладки с параметрами $n$, $k$ и $h$ на $m$ позиций вправо
  создает раскладку с параметрами $n+m$, $k+m$, $h$. Такая раскладка допустима, если
  $n+m\le w$ и $k+m\le w$.

\item Для узла $[\mbox{\lstinline{above}}]$ вводим правило $T^{k_2}_{\max(n_1, n_2)}:[\mbox{\lstinline{above}}]\:(T^{k_1}_{n_1},\;T^{k_2}_{n_2})$ 
со стоимостью, равной сумме стоимостей вывода поддеревьев,
для всех $k_1\le n_1\le w$ и $k_2 \le n_2 \le w$.

Действительно, при вертикальном соединении раскладок с параметрами
$n_1$, $k_1$, $h_1$ и $n_2$, $k_2$, $h_2$ мы получаем раскладку с размерами
$\max\:(n_1,n_2)$, $k_2$, $h_1+h_2$. Вертикальная композиция допустимых раскладок всегда допустима.

\item Для узла $[\mbox{\lstinline{beside}}]$ вводим правило
  $T^{k_1+k_2}_{\max\:(n_1,\:k_1+n_2)}:[\mbox{\lstinline{beside}}]\:(T^{k_1}_{n_1},\:T^{k_2}_{n_2})$
  для каждой комбинации $n_1, n_2, k_1, k_2$ такой, что $k_1+k_2\le\max\:(n_1,\:k_1+n_2)\le w$.
  Стоимость такого вывода равна сумме стоимостей вывода поддеревьев минус 1.
  Это может быть легко проверено из геометрических соображений.

\item Для узла $[\mbox{\lstinline{choice}}]$ вводим правило
  $T^k_n:[\mbox{\lstinline{choice}}]\:(T^k_n,\:T^k_n)$ для всех $k\le n\le w$.

  Цена есть минимум среди цен вывода для поддеревьев. Понятно, что среди двух раскладок
  с одинаковыми ширинами выбирается та, что имеет меньшую высоту.
\end{enumerate}

Для завершения описания грамматики необходимо ввести правило для стартового нетерминала $S$.
Можно добавить правило $S : r$ с тождественной функцией цены для любого $r$, или ввести
цепное правило $S: T_n^k$ с такой же функцией для всех нетерминалов $T_n^k$
(такое правило требует несущественного расширения определения BURS).

Число нетерминалов в определенной выше грамматике равно $w^2$.
Однако, число правил есть $O(w^4)$, так
как в дереве есть узлы со степенью 2. Так, приведенная BURS-реализация оптимального принтера
работает за линейное время от числа узлов в дереве документа для фиксированной ширины вывода, при
этом сложность от ширины вывода есть $O(w^4)$. Понятно, что данное сведение может быть выполнено и
для других примитивов построения дерева, которые могут иметь большую степень, но ценой
экспоненциального роста сложности по $w$.
\label{txt:bursReduction}

\subsection{Реализация сведения задачи оптимального форматирования к BURS}

В рамках данной работы была реализована
принтер-комбинаторная библиотека на языке
Haskell\footnote{\cd{http://github.com/anlun/polynomialPPCombinators}}
(см. приложение~\ref{app:1})
с тем же набором комбинаторов,
что и в~\cite{swierstra},
которая линейна относительно входного документа и полиномиальна
относительно максимальной ширины вывода за счет описанного выше сведения задачи к BURS.
Данная реализация использует низкоуровневые типы и функции из оригинальной
библиотеки~\cite{swierstra}, в то время как высокоуровневые типы и комбинаторы переопределены.

В реализации нет непосредственного использования BURS: в явном виде не задается BURS-грамматика,
нет набора нетерминалов и стандартного алгоритма обработки.
Вместо этого для каждого узла документа вычисляется ассоциативный массив, который
ставит в соответствие паре $(n, k)$ лучший (минимальный по числу строк) блок текста с параметрами
ширин $n$ и $k$. Так, в ассоциативном массиве записаны пары $((n, k), f)$, где $f$ --- это
блок текста, соответствующий оптимальному представлению с ширинами $(n, k)$. Значение
высоты $f$ есть минимальная стоимость вывода нетерминала $T^k_n$ для данного узла.
Заметим, что поскольку $f$ является конечным результатом для $T^k_n$, а не просто
последним правилом, которое нужно применить для построения ответа, то отменяется
необходимость применения в дальнейшем алгоритма свертки.
В конце, для корня дерева, представляющего документ, из
ассоциативного массива выбирается элемент минимальной стоимости.

Наибольший интерес в рамках данного исследования представляет поведение библиотеки
в худшем случае.
Реализация была апробирована на документах, полученных с помощью
функции генерации, приведенной на рис.~\ref{fig:treeToDocMy}. Они достаточно
\emph{``плохи''}, поскольку активно используют комбинаторы
\lstinline[language= Haskell]{beside} и
\lstinline[language= Haskell]{choice}, что должно приводит к экспоненциальной зависимости
числа нефакторизованных раскладок от размера дерева комбинаторов.
В функции генерации используются операторы
\lstinline[language= Haskell]{(>|<)},
\lstinline[language= Haskell]{(>-<)},
\lstinline[language= Haskell]{(>//<)}, которые являются инфиксными синоминами для
комбинаторов
\lstinline[language= Haskell]{beside},
\lstinline[language= Haskell]{above} и
\lstinline[language= Haskell]{choice} соответственно.

\begin{figure}[h!]
  \lstinputlisting[language = Haskell]{codes/AltPrettyTest.hs}
  \caption{Функция генерации деревьев для тестов производительности}
  \label{fig:treeToDocMy}
\end{figure}

Результаты времени исполнения для сравнения авторской реализации с оригинальной библиотекой
приведены в таблице~\ref{tbl:time}.
Из приведенных данных видно, что, начиная с некоторой комбинации ширины вывода и размера документа,
библиотека~\cite{swierstra} не может вычислить раскладку документа.
Значения, записанные подобно \mbox{``-($>$ 59)''}, обозначают,
что после указанного времени процесс аварийно завершился с переполнением стека.

Авторская реализация часто не показывает линейное поведение, как это ожидается при фактическом
учетверении числа узлов в документе от строчки к строчке. Дополнительные эксперименты показали
связь данного поведения с разреженностью ассоциативного массива для больших ширин.
Другими словами, для маленьких деревьев число значений в соответствующем ассоциативном массиве
сильно меньше верхней границы. С ростом размера дерева число записей растет быстрее, чем
с линейной скоростью, пока не будут достигнуты значения, близкие к верхней границе.

Кроме того, особенностью описанной реализации является то, что она не использует 
ленивые вычисления для ускорения построения оптимального текстового представления для
поданного на вход документа, а, наоборот,
форсирует большинство вычислений, что делает ее легко переносимой на языки
без встроенной ленивости.

\input{haskellTbl}


